package com.xsherl.leetcode.solution;

public class DecodeWays {

    /**
     * 动态规划，s[i]所在字符一共有两种组合情况，s[i]和s[i-1,i]
     * 所以状态转移方程
     *  dp[i] = {
     *      0,s[i] == '0' && s[i-1, i] > 26
     *      dp[i - 2],s[i] == '0' && s[i-1, i] <= 26
     *      dp[i - 1],s[i] != '0' && s[i-1, i] > 26
     *      dp[i - 1] + dp[i - 2],s[i] != '0' && s[i-1, i] > 26
     *  }
     *
     * @param s 1 <= s.length <= 100
     *          s 只包含数字，并且可能包含前导零。
     */
    public int numDecodings(String s) {
        int m = s.length();
        int[] dp = new int[m + 1];
        dp[0] = 1;
        for (int i = 0; i < m; i++){
            char c = s.charAt(i);
            if (c != '0'){
                dp[i + 1] += dp[i];
            }
            if (i > 0 && s.charAt(i - 1) > '0' && ((s.charAt(i - 1) - '0') * 10 + (c - '0') <= 26)){
                dp[i + 1] += dp[i - 1];
            }
        }
        return dp[m];
    }
    public static void main(String[] args) {
        String s = "1110";
        int i = new DecodeWays().numDecodings(s);
        System.out.println(i);
    }
}
